package com.guaoran.algorithm.sort;

import java.util.Arrays;
import java.util.Random;

/**
 * @Auth gucheng
 * @Desc 数组排序
 * @Date 2021/1/18 下午5:41
 */
public class ArraySort {


    public static void main(String[] args) {
        int[] arr = new int[10];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = new Random().nextInt(10000);
        }

        // 快速排序
        Long start = System.currentTimeMillis();
        quickSort(arr);
        System.out.println("quickSort="+Arrays.toString(arr));
        // System.out.println("quickSort==>"+(System.currentTimeMillis() - start));

        // 归并排序
        for (int i = 0; i < arr.length; i++) {
            arr[i] = new Random().nextInt(10000);
        }
        Long start2 = System.currentTimeMillis();
        mergeSort(arr);
        System.out.println("mergeSort="+Arrays.toString(arr));
        // System.out.println("mergeSort==>"+(System.currentTimeMillis() - start2));


        for (int i = 0; i < arr.length; i++) {
            arr[i] = new Random().nextInt(10000);
        }
        bubbleSort(arr);
        System.out.println("bubbleSort="+Arrays.toString(arr));


        for (int i = 0; i < arr.length; i++) {
            arr[i] = new Random().nextInt(10000);
        }
        insertSort(arr);
        System.out.println("insertSort="+Arrays.toString(arr));

        for (int i = 0; i < arr.length; i++) {
            arr[i] = new Random().nextInt(10000);
        }
        selectSort(arr);
        System.out.println("selectSort="+Arrays.toString(arr));

    }



    /**
     * 快速排序
     * @param arr
     */
    private static void quickSort(int[] arr) {
        if(arr == null || arr.length == 0){
            return;
        }

        doQuickSort(arr, 0, arr.length -1);
    }

    private static void doQuickSort(int[] arr, int start, int end) {
        if(start >= end){
            return;
        }

        int left = start;
        int right = end;
        int node = arr[start];

        while(left <= right){
            while(left <= right && arr[left] < node){
                left ++;
            }
            while(left <= right && arr[right] > node){
                right --;
            }

            if(left <= right){
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
                left ++;
                right --;
            }
        }
        doQuickSort(arr,start,right);
        doQuickSort(arr,left,end);

    }


    /**
     * 归并排序
     * @param arr
     */
    private static void mergeSort(int[] arr) {
        if(arr == null || arr.length == 0){
            return;
        }
        int[] temp = new int[arr.length];
        doMerge(arr, 0, arr.length -1 ,temp);
    }

    private static void doMerge(int[] arr, int start, int end, int[] temp) {
        if(start >= end){
            return;
        }

        int mid = (start + end) / 2;
        doMerge(arr,start,mid,temp);
        doMerge(arr,mid+1,end,temp);
        doMergeSort(arr,start,mid,end,temp);
    }

    private static void doMergeSort(int[] arr, int start, int mid, int end, int[] temp) {
        int left = start;
        int right = mid +1;
        int index = start;

        while(left <= mid && right <= end){
            if(left <= mid && arr[left] < arr[right]){
                temp[index++] = arr[left++];
            }else {
                temp[index++] = arr[right++];
            }
        }
        while(left <= mid){
            temp[index++] = arr[left++];
        }
        while(right <= end){
            temp[index++] = arr[right++];
        }

        for (int i = start; i <= end ; i++) {
            arr[i] = temp[i];
        }
    }


    /**
     * 冒泡
     * @param arr
     */
    public static void bubbleSort(int[] arr){
        if(arr == null || arr.length == 0){
            return;
        }

        for (int i = 0; i < arr.length; i++) {
            for (int j = 1; j < arr.length; j++) {
                if(arr[j] < arr[j-1]){
                    int temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                }
            }
        }

    }

    /**
     * 插入
     * @param arr
     */
    public static void insertSort(int[] arr){
        if(arr == null || arr.length == 0){
            return;
        }
        for (int i = 1; i < arr.length; i++) {
            int node = arr[i];
            int j =  i -1;
            while(j >= 0 && arr[j] > node){
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = node;
        }
    }

    /**
     * 选择
     * @param arr
     */
    public static void selectSort(int[] arr){
        if(arr == null || arr.length == 0){
            return;
        }

        for (int i = 0; i < arr.length; i++) {
            int min = i;
            for (int j = i+1; j < arr.length; j++) {
                if(arr[min] > arr[j]){
                    min = j;
                }
            }
            if(min != i){
                int temp = arr[i];
                arr[i] = arr[min];
                arr[min] = temp;
            }
        }
    }

}
